#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 这个题目思考的时候将target和矩阵右上角的元素进行比较，如果target大于了右上角的元素
        // 代表这一行的元素都不是target那么就让i++，然后去比较下一行的右上角元素，如果此时这个右上角的元素大于了
        // target代表这一列的元素都不可能是target这个元素，让j--，这样就能够快速的在一个矩阵中找到target元素了
        int i = 0;
        int j = matrix[0].size() - 1;
        int m = matrix.size();
        int n = matrix[0].size();
        while(i<m&&j>=0)
        {
            if(matrix[i][j]>target)
            {
                //右上角的元素大于了target
                //代表这一列的元素都不可能是target
                j--;
            }
            else if(matrix[i][j]<target)
            {
                //右上角的元素小于了target
                //代表这一行的元素都不可能是target了
                i++;
            }
            else
            {
                //这个位置就是target
                return true;
            }
        }
        //矩阵已经排除完了，没有这个元素返回false
        return false;   
    }
};